In recent years, wireless mesh networks (WMNs) have emerged as a new technology that can be used to install wireless infrastructure in residential, campus, community, and even metropolitan areas. In a mesh network each network node is connected to one or more other nodes of the network. The operation of wireless mesh networks is similar to the operation of a network with fixed routers with the exception that the links established between the network nodes are wireless links. Typically, a wireless mesh network includes several nodes that have a wired/wireless connection to a wired infrastructure, in particular to the Internet. These nodes are referred to as mesh gateways. By establishing a (multi-hop) link to one of these mesh gateways the remaining mesh nodes of the network can also access the Internet.
Existing routing strategies in WMNs mostly focus on forwarding traffic between mesh nodes and mesh gateways due to a widespread assumption that the majority of traffic carried in WMNs either originates or terminates outside the WMNs. Due to this assumption, existing routing strategies usually form one or multiple forwarding trees rooted at the mesh gateways, as described for instance in A. Raniwala, T. Chiueh, Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network, in IEEE Infocom 2005, March 2005.
Intra-mesh traffic (traffic that both originates and terminates inside WMNs) has received little attention so far. However, a recent measurement study of wireless campus networks shows that intra-mesh traffic can play an important role (T. Henderson, D. Kotz, and I. Abyzov, The changing usage of a mature campus-wide wireless network, ACM MobiCom 2004). For example, this measurement study showed that the percentage of intra-mesh traffic increased from 35.5% to 69.6% between 2001 and 2004. While this trend may not hold for all WMNs' usage and scenarios, it indicates that intra-mesh traffic can play an important role and also emphasizes the dynamic nature of WMNs' usage. For this reason, WMNs should provide efficient routing mechanisms for intra-mesh traffic.
FIG. 1 illustrates a wireless mesh network WMN 1 with a multitude of mesh nodes 2. The wireless connections between the mesh nodes 2 are indicated by solid lines. Besides the ordinary mesh nodes 2, the WMN 1 includes two mesh gateways 3 that are connected via a wired/wireless link to access routers 4 of a wired network 5. Until recently, as indicated in FIG. 1 by the dashed lines, intra-mesh traffic between two mesh nodes 2a, 2b is routed in a hop-by-hop manner inside the WMN 2. This routing strategy is widely used in WMNs and is described in some more detail e.g., in R. Draves, J. Padhye, and B. Zill, Routing in Multi-radio, Multi-hop Wireless Mesh Networks, ACM MobiCom 2004 or in J. Bicket, D. Aguayo, S. Biswas, and R. Morris, Architecture and Evaluation of an Unplanned 802.11b Mesh Network, ACM Mobicom 2005.
As illustrated in FIG. 2, in which like numerals are used for like components with respect to FIG. 1, it is also possible to divide the path between two mesh nodes 2a, 2b into three segments: (A) mesh node 2 to mesh gateway 3a, (B) between two mesh gateways 3a, 3b via the wired network 5, and (C) mesh gateway 3b to mesh node 2b. The rational behind this is that the wired network 5 can serve as a backbone to interconnect mesh nodes 2 in the WMN 1.
However, there is an essential problem associated with the aforementioned approaches: Depending on the link characteristics between the mesh gateways, it may or may not make sense to route intra-mesh traffic through the wired network. For example, if the wired network is over-provisioned, e.g., mesh gateways are connected by high-bandwidth links, it makes sense to route intra-mesh traffic through the wired network. However, if the wired network is under-provisioned, e.g., mesh gateways are connected by low-bandwidth links such as UMTS uplinks, it does not make sense to route intra-mesh traffic through the wired network. In this case, intra-mesh traffic unnecessarily competes with traffic between mesh and infrastructure network, and causes congestion at the mesh gateways. One way to solve this problem would be to define a routing policy at all mesh nodes that dictates whether intra-mesh traffic should be routed via the wired network. This routing policy is manually configured depending on the characteristics of the links connecting the mesh gateways. However, this solution is rather cumbersome.